#include "SortThread.h"
#include "../gui/BarWidget.h"
#include <QElapsedTimer>
#include <functional>
#include <algorithm>
#include <QThread>            // ★ 新增：检测当前线程
#include <future>
#include <tuple>        // std::tie

SortThread::SortThread(QObject *p): QThread(p) {
}


bool SortThread::isPaused() {
    QMutexLocker lk(&m_mutex);
    return m_pause;
}

double SortThread::currentSpeed() {
    QMutexLocker lk(&m_mutex);
    return m_cfg.speedMult;
}

void SortThread::updateSpeed(double s) {
    QMutexLocker lk(&m_mutex);
    m_cfg.speedMult = s;
}


/* =================================================================
   自实现 IntroSort  (快排 + 堆排 + 插排)   —— 用于 STDSort 算法
   ================================================================= */
static void insertionRange(QVector<uint32_t> &a, int l, int r,
                           SortStats &st, SortThread *self, QElapsedTimer &tim) {
    for (int i = l + 1; i <= r; ++i) {
        uint32_t key = a[i];
        int j = i - 1;
        while (j >= l && (++st.compare, a[j] > key)) {
            a[j + 1] = a[j];
            ++st.swap;
            --j;
            pushFrame(a, st, self, tim);
        }
        a[j + 1] = key;
        ++st.swap;
        pushFrame(a, st, self, tim);
    }
}

/* =======================================================
   并行归并排序 · 轮番单步
   ======================================================= */
static void parMerge(QVector<uint32_t>& a,
                     SortStats& st, SortThread* self,
                     QElapsedTimer& tim)
{
    const int N = a.size();
    QVector<uint32_t> buf(N);
    const int tidCnt = std::clamp((N + 31) / 32, 1, 32);

    for (int size = 1; size < N; size <<= 1)
    {
        /* 把本轮所有归并任务收集到 jobs -------------------- */
        struct Job { int l,m,r,i,j,k,pid; bool mergeDone; };
        std::vector<Job> jobs;
        for (int l = 0, pid = 0; l < N; l += size<<1, ++pid)
        {
            int m = std::min(l + size,     N);
            int r = std::min(l + (size<<1), N);
            if (m >= r) continue;
            jobs.push_back({l,m,r,l,m,l,pid % tidCnt,false});
        }

        /* ---------------- 轮番执行 ------------------------ */
        bool work = true;
        while (work)
        {
            work = false;
            for (auto &t : jobs)
            {
                /* 线程颜色帧（无等待） */
                for (int x = t.l; x < t.r; ++x) self->m_tag[x] = t.pid;
                pushFrame(a, st, self, tim, 0.0);

                /* —— 阶段 A：归并到 buf —— */
                if (!t.mergeDone)
                {
                    if (t.i < t.m && (t.j >= t.r ||
                                      (++st.compare, a[t.i]<=a[t.j])))
                        buf[t.k++] = a[t.i++];
                    else
                        buf[t.k++] = a[t.j++];
                    ++st.swap;

                    if (t.k == t.r) t.mergeDone = true;
                    work = true;
                    continue;                 // 下一线程
                }

                /* —— 阶段 B：回写到 a —— */
                if (t.l < t.r)
                {
                    a[t.l] = buf[t.l];
                    ++st.swap;
                    ++t.l;                    // 前移写回指针
                    pushFrame(a, st, self, tim, 1.0 / tidCnt);
                    work = true;
                }
            }
        }
    }
}

/* =======================================================
   并行快速排序 · 轮番单步（双枢轴）
   ======================================================= */
static void parQuick(QVector<uint32_t>& a,
                     SortStats& st, SortThread* self,
                     QElapsedTimer& tim)
{
    const int N = a.size();
    const int tidCnt = std::clamp((N + 31) / 32, 1, 32);

    /* 用显式栈记录待处理子区间 + 状态 -------------------- */
    struct Node {
        int l,r,step,pid;        // step: 0=未划分, 1=左子栈入,
                                 // 2=中子栈入, 3=右子栈入 (已完成)
        int lt,gt, i,j;
        uint32_t p,q;
    };
    std::vector<Node> stk{{0,N-1,0,0}};

    while (!stk.empty())
    {
        /* 轮番取 tidCnt 个节点作业 ------------------------ */
        int batch = std::min<int>(tidCnt, stk.size());
        for (int tix = 0; tix < batch; ++tix)
        {
            Node &nd = stk[stk.size()-1-tix];     // 后进先服务

            /* 颜色帧 */
            for (int x = nd.l; x <= nd.r; ++x) self->m_tag[x] = nd.pid;
            pushFrame(a, st, self, tim, 0.0);

            /* ---------- 单步处理 ---------- */
            if (nd.step == 0)            /* ── 初始化划分 ── */
            {
                if (nd.l >= nd.r) { nd.step = 3; continue; }
                if (a[nd.l] > a[nd.r]) std::swap(a[nd.l],a[nd.r]),++st.swap;
                nd.p = a[nd.l]; nd.q = a[nd.r];
                nd.lt = nd.l+1; nd.gt = nd.r-1; nd.i = nd.lt;
                nd.step = 1;                         // 转到划分循环
            }

            if (nd.step == 1)            /* ── 划分循环 ── */
            {
                if (nd.i <= nd.gt)
                {
                    if (++st.compare && a[nd.i] < nd.p) {
                        std::swap(a[nd.i], a[nd.lt]); ++st.swap; ++nd.lt;
                    } else if (++st.compare && a[nd.i] > nd.q) {
                        while (nd.gt > nd.i && a[nd.gt] > nd.q)
                            { --nd.gt; ++st.compare; }
                        std::swap(a[nd.i], a[nd.gt]); ++st.swap; --nd.gt;
                        if (a[nd.i] < nd.p) {
                            std::swap(a[nd.i], a[nd.lt]); ++st.swap; ++nd.lt;
                        }
                    }
                    ++nd.i;
                    pushFrame(a, st, self, tim, 1.0 / tidCnt);
                    continue;                       // 下一线程
                }
                /* 划分完成：放枢轴 */
                --nd.lt; ++nd.gt;
                std::swap(a[nd.l], a[nd.lt]); ++st.swap;
                std::swap(a[nd.r], a[nd.gt]); ++st.swap;
                pushFrame(a, st, self, tim, 1.0 / tidCnt);

                nd.step = 2;                       // 下一阶段
            }

            if (nd.step == 2)            /* ── push 子区间 ── */
            {
                /* 生成 3 个子区间，pid 派生 */
                int basePid = nd.pid * 3;
                stk.push_back({nd.l,      nd.lt-1,0, (basePid+1)%tidCnt});
                stk.push_back({nd.lt+1,   nd.gt-1,0, (basePid+2)%tidCnt});
                stk.push_back({nd.gt+1,   nd.r,   0,(basePid+3)%tidCnt});
                nd.step = 3;
            }
        }

        /* 移除已完成节点 */
        while (!stk.empty() && stk.back().step == 3) stk.pop_back();
    }
}


/* =======================================================
   并行 TimSort（轮流块插排 + 轮番单步归并）
   ======================================================= */
static void parTim(QVector<uint32_t> &a,
                   SortStats &st, SortThread *self, QElapsedTimer &tim)
{
    const int N   = a.size();
    constexpr int RUN = 32;                  // 块大小 ≈ minRun
    const int runCnt = (N + RUN - 1) / RUN;  // 总块数

    /* ---------- 1. 轮流插排所有块 ---------- */
    QVector<int> start(runCnt);
    for (int i = 0; i < runCnt; ++i) start[i] = i * RUN;

    for (int offset = 1; offset < RUN; ++offset)
    {
        for (int rid = 0; rid < runCnt; ++rid)
        {
            int l = start[rid];
            int r = std::min(l + RUN - 1, N - 1);
            if (l + offset > r) continue;

            /* 仅改颜色 —— 不休眠 */
            for (int k = l; k <= r; ++k) self->m_tag[k] = rid;
            pushFrame(a, st, self, tim, 0.0);

            /* 单步插入（改动数据） */
            int i = l + offset;
            uint32_t key = a[i];
            int j = i - 1;
            while (j >= l && (++st.compare, a[j] > key))
            {
                a[j + 1] = a[j];
                ++st.swap;
                --j;
            }
            a[j + 1] = key;
            ++st.swap;

            pushFrame(a, st, self, tim);            // 默认 1.0
        }
    }

    /* ---------- 2. 轮番归并所有块 ---------- */
    QVector<uint32_t> buf(N);

    for (int size = RUN; size < N; size <<= 1)
    {
        struct Task { int l,m,r,pid; int i,j,k; };
        std::vector<Task> jobs;

        for (int l = 0, pid = 0; l < N; l += size << 1, ++pid)
        {
            int m = std::min(l + size,     N);
            int r = std::min(l + (size<<1), N);
            if (m >= r) continue;
            jobs.push_back({l,m,r,pid, l, m, l});
        }

        /* —— 轮番把数据写入 buf —— */
        bool work = true;
        while (work)
        {
            work = false;
            for (auto &t : jobs)
            {
                if (t.k < t.r)
                {
                    work = true;

                    /* 着色帧（仅颜色） */
                    for (int x = t.l; x < t.r; ++x) self->m_tag[x] = t.pid;
                    pushFrame(a, st, self, tim, 0.0);

                    /* 搬 1 个元素 */
                    if (t.i < t.m && (t.j >= t.r ||
                                      (++st.compare, a[t.i] <= a[t.j])))
                        buf[t.k++] = a[t.i++];
                    else
                        buf[t.k++] = a[t.j++];
                    ++st.swap;

                    pushFrame(a, st, self, tim, 0.0);    // 数据帧
                }
            }
        }

        /* —— 轮番回写到 a —— */
        bool back = true;
        while (back)
        {
            back = false;
            for (auto &t : jobs)
            {
                if (t.l < t.r)
                {
                    back = true;

                    int pos = t.l++;

                    self->m_tag[pos] = t.pid;       // 颜色帧
                    pushFrame(a, st, self, tim, 0.0);

                    a[pos] = buf[pos];
                    ++st.swap;

                    pushFrame(a, st, self, tim);    // 数据帧
                }
            }
        }
    }
}


/* ---- 发帧 ---- */
static inline void pushFrame(const QVector<uint32_t>& src,
                             SortStats&              st,
                             SortThread*             self,
                             QElapsedTimer&          tim,
                             double                  delayFactor)   // ★ rename
{
    if (QThread::currentThread() != self) return;

    st.ms = tim.elapsed();

    QVector<uint32_t> dataSnap(src);
    QVector<int>      tagSnap (self->m_tag);

    emit self->frameReady(dataSnap, tagSnap, st);

    /* 仅当 delayFactor>0 才休眠；可按比例放大/缩小 */
    if (delayFactor > 0.0)
    {
        int base = std::max(1, int(20 * delayFactor / self->currentSpeed()));
        QThread::msleep(base);
    }

    if (self->isPaused()) throw 0;
}


/* ===== Java-style TimSort helpers ================================= */
namespace TimJava {
    constexpr int MIN_MERGE = 32;

    static int minRunLength(int n) {
        int r = 0;
        while (n >= MIN_MERGE) {
            r |= (n & 1);
            n >>= 1;
        }
        return n + r;
    }

    /* --- Binary-insertion sort (内层使用) --- */
    static void binaryInsertion(QVector<uint32_t> &a, int lo, int hi,
                                SortStats &st, SortThread *self, QElapsedTimer &tim) {
        for (int i = lo + 1; i <= hi; ++i) {
            uint32_t key = a[i];
            int left = lo, right = i;
            while (left < right) {
                int mid = (left + right) >> 1;
                ++st.compare;
                (key < a[mid]) ? right = mid : left = mid + 1;
            }
            for (int j = i; j > left; --j) {
                a[j] = a[j - 1];
                ++st.swap;
            }
            a[left] = key;
            ++st.swap;
        }
        pushFrame(a, st, self, tim);
    }

    /* --- 归并 (无 gallop，方便演示) --- */
    static void merge(QVector<uint32_t> &a, int base1, int len1,
                      int base2, int len2,
                      SortStats &st, SortThread *self, QElapsedTimer &tim) {
        QVector<uint32_t> left(len1);
        std::copy_n(a.begin() + base1, len1, left.begin());

        int i = 0, j = base2, k = base1;
        while (i < len1 && j < base2 + len2) {
            ++st.compare;
            if (left[i] <= a[j]) {
                a[k++] = left[i++];
                pushFrame(a, st, self, tim);
            } else {
                a[k++] = a[j++];
                pushFrame(a, st, self, tim);
            }
            ++st.swap;
        }
        while (i < len1) {
            a[k++] = left[i++];
            ++st.swap;
        }

        pushFrame(a, st, self, tim);
    }
} // namespace TimJava

/* ---------- Bitonic ---------- */
static void bitonicSort(QVector<uint32_t> &a, SortStats &st,
                        SortThread *self, QElapsedTimer &tim) {
    const int N = a.size();
    int k;
    for (k = 1; k < N; k <<= 1);
    for (int size = 2; size <= k; size <<= 1) {
        for (int sub = size >> 1; sub > 0; sub >>= 1) {
            for (int i = 0; i < N; ++i) {
                int j = i ^ sub;
                if (j > i) {
                    bool dir = ((i & size) == 0);
                    ++st.compare;
                    if ((a[i] > a[j]) == dir) {
                        std::swap(a[i], a[j]);
                        ++st.swap;
                        pushFrame(a, st, self, tim);
                    }
                }
            }
        }
    }
}

static void heapify(QVector<uint32_t> &a, int n, int i, int base,
                    SortStats &st, SortThread *self, QElapsedTimer &tim) {
    while (true) {
        int mx = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && (++st.compare, a[base + l] > a[base + mx])) mx = l;
        if (r < n && (++st.compare, a[base + r] > a[base + mx])) mx = r;
        if (mx == i) break;
        std::swap(a[base + i], a[base + mx]);
        ++st.swap;
        pushFrame(a, st, self, tim);
        i = mx;
    }
}

static void heapSortRange(QVector<uint32_t> &a, int l, int r,
                          SortStats &st, SortThread *self, QElapsedTimer &tim) {
    int n = r - l + 1;
    for (int i = n / 2 - 1; i >= 0; --i) heapify(a, n, i, l, st, self, tim);
    for (int end = n - 1; end > 0; --end) {
        std::swap(a[l], a[l + end]);
        ++st.swap;
        pushFrame(a, st, self, tim);
        heapify(a, end, 0, l, st, self, tim);
    }
}

static void introSort(QVector<uint32_t> &a, int l, int r, int depth,
                      SortStats &st, SortThread *self, QElapsedTimer &tim) {
    const int INSERT_CUT = 16;
    if (r - l <= INSERT_CUT) {
        insertionRange(a, l, r, st, self, tim);
        return;
    }
    if (depth == 0) {
        heapSortRange(a, l, r, st, self, tim);
        return;
    }

    uint32_t pivot = a[(l + r) / 2];
    int i = l, j = r;
    while (i <= j) {
        while ((++st.compare, a[i] < pivot)) ++i;
        while ((++st.compare, a[j] > pivot)) --j;
        if (i <= j) {
            if (i < j) {
                std::swap(a[i], a[j]);
                ++st.swap;
                pushFrame(a, st, self, tim);
            }
            ++i;
            --j;
        }
    }
    if (l < j) introSort(a, l, j, depth - 1, st, self, tim);
    if (i < r) introSort(a, i, r, depth - 1, st, self, tim);
}

/* ---------- 全算法实现 ---------- */
static void cpuSort(QVector<uint32_t> &a, Algo algo, SortThread *self) {
    const int N = a.size();
    SortStats st;
    QElapsedTimer timer;
    timer.start();

    auto pushMaybe = [&](int &c) {
        if (++c % std::max(1, N / 64) == 0) pushFrame(a, st, self, timer);
    };
    int c = 0;

    try {
        /* 1 Bubble */
        if (algo == Algo::Bubble) {
            for (int i = 0; i < N - 1; ++i)
                for (int j = 0; j < N - 1 - i; ++j) {
                    ++st.compare;
                    if (a[j] > a[j + 1]) {
                        std::swap(a[j], a[j + 1]);
                        ++st.swap;
                        pushMaybe(c);
                    }
                }
        }
        /* 2 Insertion */
        else if (algo == Algo::Insertion) {
            for (int i = 1; i < N; ++i) {
                uint32_t key = a[i];
                int j = i - 1;
                while (j >= 0 && (++st.compare, a[j] > key)) {
                    a[j + 1] = a[j];
                    ++st.swap;
                    --j;
                    pushMaybe(c);
                }
                a[j + 1] = key;
                pushMaybe(c);
            }
        }
        /* 3 Selection */
        else if (algo == Algo::Selection) {
            for (int i = 0; i < N - 1; ++i) {
                int m = i;
                for (int j = i + 1; j < N; ++j) {
                    ++st.compare;
                    if (a[j] < a[m]) m = j;
                }
                if (m != i) {
                    std::swap(a[i], a[m]);
                    ++st.swap;
                    pushMaybe(c);
                }
            }
        }
        /* 4 Binary Insertion */
        else if (algo == Algo::BinaryInsertion) {
            for (int i = 1; i < N; ++i) {
                uint32_t key = a[i];
                int lo = 0, hi = i;
                while (lo < hi) {
                    int mid = (lo + hi) / 2;
                    ++st.compare;
                    (a[mid] > key) ? hi = mid : lo = mid + 1;
                }
                for (int j = i; j > lo; --j) {
                    a[j] = a[j - 1];
                    ++st.swap;
                    pushMaybe(c);
                }
                a[lo] = key;
                pushMaybe(c);
            }
        }
        /* 5 Shell (Knuth gap) */
        else if (algo == Algo::Shell) {
            int gap = 1;
            while (gap < N / 3) gap = gap * 3 + 1;
            for (; gap > 0; gap /= 3)
                for (int i = gap; i < N; ++i) {
                    uint32_t key = a[i];
                    int j = i;
                    while (j >= gap && (++st.compare, a[j - gap] > key)) {
                        a[j] = a[j - gap];
                        j -= gap;
                        ++st.swap;
                        pushMaybe(c);
                    }
                    a[j] = key;
                    pushMaybe(c);
                }
        }
        /* 6 Merge */
        else if (algo == Algo::Merge) {
            QVector<uint32_t> buf(N);
            for (int sz = 1; sz < N; sz *= 2)
                for (int l = 0; l < N; l += 2 * sz) {
                    int m = std::min(l + sz, N), r = std::min(l + 2 * sz, N);
                    int i = l, j = m, k = l;
                    while (i < m || j < r) {
                        uint32_t v;
                        if (j >= r || (i < m && (++st.compare, a[i] < a[j]))) v = a[i++];
                        else v = a[j++];
                        buf[k++] = v;
                        ++st.swap;
                    }
                    std::copy(buf.begin() + l, buf.begin() + r, a.begin() + l);
                    pushFrame(a, st, self, timer);
                }
        }
        /* 7 Quick */
        else if (algo == Algo::Quick) {
            std::vector<std::pair<int, int> > S{{0, N - 1}};
            while (!S.empty()) {
                auto [l,r] = S.back();
                S.pop_back();
                if (l >= r) continue;
                uint32_t pv = a[r];
                int i = l - 1;
                for (int j = l; j < r; ++j) {
                    ++st.compare;
                    if (a[j] < pv) {
                        std::swap(a[++i], a[j]);
                        ++st.swap;
                        pushMaybe(c);
                    }
                }
                std::swap(a[i + 1], a[r]);
                ++st.swap;
                pushFrame(a, st, self, timer);
                S.push_back({l, i});
                S.push_back({i + 2, r});
            }
        }
        /* 8 Dual-Pivot Quick */
        else if (algo == Algo::DualPivotQuick) {
            std::vector<std::pair<int, int> > S{{0, N - 1}};
            while (!S.empty()) {
                auto [l,r] = S.back();
                S.pop_back();
                if (l >= r) continue;

                // 交换以保证左边基准 <= 右边基准
                if (a[l] > a[r]) std::swap(a[l], a[r]);
                uint32_t p = a[l], q = a[r];

                int lt = l + 1, gt = r - 1, i = lt;
                while (i <= gt) {
                    if (++st.compare && a[i] < p) {
                        std::swap(a[i], a[lt]);
                        ++st.swap;
                        ++lt;
                    } else if (++st.compare && a[i] > q) {
                        while (gt > i && a[gt] > q) {
                            --gt;
                            ++st.compare;
                        }
                        std::swap(a[i], a[gt]);
                        ++st.swap;
                        --gt;
                        if (a[i] < p) {
                            std::swap(a[i], a[lt]);
                            ++st.swap;
                            ++lt;
                        }
                    }
                    ++i;
                    pushMaybe(c);
                }

                --lt;
                ++gt;
                std::swap(a[l], a[lt]);
                ++st.swap;
                std::swap(a[r], a[gt]);
                ++st.swap;
                pushFrame(a, st, self, timer);

                S.push_back({l, lt - 1});
                S.push_back({lt + 1, gt - 1});
                S.push_back({gt + 1, r});
            }
        }

        /* 9 Heap */
        else if (algo == Algo::Heap) {
            std::function<void(int, int)> sift;
            sift = [&](int n, int i) {
                int mx = i, l = 2 * i + 1, r = 2 * i + 2;
                if (l < n && (++st.compare, a[l] > a[mx])) mx = l;
                if (r < n && (++st.compare, a[r] > a[mx])) mx = r;
                if (mx != i) {
                    std::swap(a[i], a[mx]);
                    ++st.swap;
                    pushFrame(a, st, self, timer);
                    sift(n, mx);
                }
            };
            for (int n = N; n > 1; --n) {
                for (int i = n / 2 - 1; i >= 0; --i) sift(n, i);
                std::swap(a[0], a[n - 1]);
                ++st.swap;
                pushFrame(a, st, self, timer);
            }
        }
        /* 10 Counting */
        else if (algo == Algo::Counting) {
            uint32_t mx = *std::max_element(a.begin(), a.end());
            QVector<uint32_t> hist(mx + 1);
            for (uint32_t v: a) {
                ++hist[v];
                ++st.swap;
                pushMaybe(c);
            }
            int k = 0;
            for (uint32_t v = 0; v <= mx; ++v)
                while (hist[v]--) {
                    a[k++] = v;
                    ++st.swap;
                    pushMaybe(c);
                }
        }
        /* 11 Bucket */
        else if (algo == Algo::Bucket) {
            uint32_t mx = *std::max_element(a.begin(), a.end());
            int B = 10;
            std::vector<std::vector<uint32_t> > bk(B);
            for (uint32_t v: a) {
                bk[(uint64_t) v * B / (mx + 1)].push_back(v);
                ++st.swap;
                pushMaybe(c);
            }
            int k = 0;
            for (auto &b: bk) {
                std::sort(b.begin(), b.end());
                for (uint32_t v: b) {
                    a[k++] = v;
                    ++st.swap;
                    pushMaybe(c);
                }
            }
        }
        /* 12  Radix-10 (LSD) ------------------------------------------------ */
        else if (algo == Algo::Radix) {
            constexpr int BASE = 10; // 10 进制基数
            QVector<uint32_t> buf(N);

            uint32_t maxVal = *std::max_element(a.begin(), a.end());
            int passCnt = 0;
            while (maxVal > 0) {
                maxVal /= BASE;
                ++passCnt;
            }
            if (passCnt == 0) passCnt = 1; // 至少一趟

            for (int pass = 0; pass < passCnt; ++pass) {
                int count[BASE] = {0};
                uint32_t pow10 = 1;
                for (int i = 0; i < pass; ++i) pow10 *= BASE;

                /* 1. 计数当前位 */
                for (uint32_t v: a) {
                    int digit = (v / pow10) % BASE;
                    ++count[digit];
                    ++st.swap;
                    pushMaybe(c);
                }

                /* 2. 前缀和 -> pos */
                int pos[BASE];
                pos[0] = 0;
                for (int i = 1; i < BASE; ++i) pos[i] = pos[i - 1] + count[i - 1];

                /* 3. 写入缓冲区 */
                for (uint32_t v: a) {
                    int digit = (v / pow10) % BASE;
                    buf[pos[digit]++] = v;
                    ++st.swap;
                    pushMaybe(c);
                }

                /* 4. 回写到 a 并可视化 */
                for (int i = 0; i < N; ++i) {
                    a[i] = buf[i];
                    ++st.swap;
                    pushMaybe(c);
                }

                pushFrame(a, st, self, timer); // 每 pass 推一帧
            }
        }

        /* 13  TimSort (可视化简化版) --------------------- */
        else if (algo == Algo::Tim) {
            using namespace TimJava;

            struct Run {
                int base, len;
            };
            std::vector<Run> runStack;

            /* 1. 枚举自然 run，并扩展到 minRun */
            for (int i = 0; i < N;) {
                int runHi = i + 1;
                if (runHi == N) { runHi = N; } else {
                    /* 找到升序 run */
                    while (runHi < N && a[runHi - 1] <= a[runHi]) ++runHi;
                }
                int runLen = runHi - i;

                /* 若不足 minRun，用 binaryInsertion 扩展 */
                int minRun = minRunLength(N);
                if (runLen < minRun) {
                    int force = std::min(minRun, N - i);
                    binaryInsertion(a, i, i + force - 1, st, self, timer);
                    runLen = force;
                }

                runStack.push_back({i, runLen});
                i += runLen;

                /* 2. 维护 runStack 不变式 */
                while (runStack.size() > 1) {
                    int n = runStack.size();
                    int lenX = runStack[n - 1].len;
                    int lenY = runStack[n - 2].len;
                    int lenZ = (n > 2) ? runStack[n - 3].len : INT_MAX;

                    if (lenZ <= lenY + lenX || lenY <= lenX) {
                        if (lenZ < lenX) {
                            /* merge Z & Y */
                            TimJava::merge(a, runStack[n - 3].base, lenZ,
                                           runStack[n - 2].base, lenY,
                                           st, self, timer);
                            runStack[n - 2].base = runStack[n - 3].base;
                            runStack[n - 2].len += lenZ;
                            runStack.erase(runStack.begin() + n - 3);
                        } else {
                            /* merge Y & X */
                            TimJava::merge(a, runStack[n - 2].base, lenY,
                                           runStack[n - 1].base, lenX,
                                           st, self, timer);
                            runStack[n - 2].len += lenX;
                            runStack.pop_back();
                        }
                    } else break;
                }
            }

            /* 3. 清空栈 */
            while (runStack.size() > 1) {
                int n = runStack.size();
                TimJava::merge(a, runStack[n - 2].base, runStack[n - 2].len,
                               runStack[n - 1].base, runStack[n - 1].len,
                               st, self, timer);
                runStack[n - 2].len += runStack[n - 1].len;
                runStack.pop_back();
            }
        }
        /* 14  STDSort (一次完成，前后各推一帧) */
        if (algo == Algo::STDSort) {
            pushFrame(a, st, self, timer); // 起始状态
            int maxDepth = 2 * int(std::log(N));
            introSort(a, 0, N - 1, maxDepth, st, self, timer);
            pushFrame(a, st, self, timer); // 完结状态
        }
        /* 18  Bitonic */
        else if (algo == Algo::Bitonic) {
            bitonicSort(a, st, self, timer);
        }
        pushFrame(a, st, self, timer); // 最后一帧
    } catch (int) {
    }
}


/* ---------- 线程接口 ---------- */
void SortThread::applyConfig(SortConfig c) {
    QMutexLocker lk(&m_mutex);
    if (c.shuffle != m_cfg.shuffle) m_shuffleReq = true;
    m_cfg = c;
    m_pause = true;
    m_wait.wakeAll();
}

void SortThread::togglePause() {
    QMutexLocker lk(&m_mutex);
    m_pause = !m_pause;
    if (!m_pause) m_wait.wakeAll();
}

void SortThread::forceShuffle() {
    QMutexLocker lk(&m_mutex);
    m_shuffleReq = true;
    m_pause = true;
    m_wait.wakeAll();
}

void SortThread::forcePause() {
    QMutexLocker lk(&m_mutex);
    m_pause = true;
}

void SortThread::stop() {
    QMutexLocker lk(&m_mutex);
    m_abort = true;
    m_wait.wakeAll();
}

void SortThread::run() {
    int curN = 0;
    while (true) {
        {
            QMutexLocker lk(&m_mutex);
            if (m_abort) break;
            if (m_pause) m_wait.wait(&m_mutex);
            if (m_abort) break;
        }

        SortConfig cfg; {
            QMutexLocker lk(&m_mutex);
            cfg = m_cfg;
        }

        /* 尺寸变化：重分配 host/tag */
        if (cfg.N != curN) {
            curN = cfg.N;
            m_host.resize(curN);
            m_tag.resize(curN);
            m_shuffleReq = true;
        }

        /* 打乱显示 */
        if (m_shuffleReq) {
            applyShuffle(m_host, cfg.shuffle);
            std::fill(m_tag.begin(), m_tag.end(), -1);
            m_shuffleReq = false;
            emit frameReady(m_host, m_tag, {}); {
                QMutexLocker lk(&m_mutex);
                m_pause = true;
            }
            continue;
        }

        SortStats st{};
        QElapsedTimer timer;
        timer.start();

        /* 选择算法 */
        if (cfg.algo == Algo::ParMerge) {
            try {
                parMerge(m_host, st, this, timer);
            } catch (int) {}           // 与其他算法保持一致，可响应暂停
        }
        else if (cfg.algo == Algo::ParQuick)
            try {
                parQuick(m_host, st, this, timer);
            } catch (int) {}           // 与其他算法保持一致，可响应暂停
        else if (cfg.algo == Algo::ParTim)
            try {
                parTim(m_host, st, this, timer);
            } catch (int) {}           // 与其他算法保持一致，可响应暂停
        else
            cpuSort(m_host, cfg.algo, this);

        /* 最后一帧（并行算法内部已推；顺排已在 cpuSort 推） */
        {
            QMutexLocker lk(&m_mutex);
            m_pause = true;
        }
    }
}
